// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
public class CountCompleteTreeNodes {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }

        return func(root,1,mostLeft(root,1));
    }

    //参数cur 表示当前节点，lever表示当前节点在第几层，h表示整棵树的高度
    public int func(TreeNode cur, int lever, int h) {
        if(lever == h){  //表示在最后一层
            return 1;
        }

        //cur右树的最左节点能够走到最后一层，表示cur的左树一定是满二叉树
        if(mostLeft(cur.right,lever+1) == h){
            return (1 << (h-lever) ) + func(cur.right,lever+1,h);
        }else{
            //cur右树的最左节点不能够走到最后一层，表示cur的右树一定是满二叉树
            return (1 << (h-lever-1) ) + func(cur.left,lever+1,h);
        }
    }

    public int mostLeft(TreeNode cur, int lever) {
        while (cur != null){
            lever++;
            cur = cur.left;
        }
        return lever-1;
    }


}
